package com.hdu.other.monotonyQueue;

public class lc239 {
    class Solution {
        private static final int MAX_N = 100000;
        private static final int[] ARR = new int[MAX_N];
        private static int H = 0, T = 0;
        public int[] maxSlidingWindow(int[] nums, int k) {
            refresh();
            int[] ans = new int[nums.length - k + 1];
            int index = 0;
            for (int i = 0; i < k; i++)
            {
                add(nums, i);
            }
            ans[index++] = max(nums);
            for (int i = k; i < nums.length; i++)
            {
                del(i - k);
                add(nums, i);
                ans[index++] = max(nums);
            }
            return ans;
        }

        void refresh()
        {
            H = T = 0;
        }

        void add(int[] nums, int index)
        {
            while (H < T && nums[index] >= nums[ARR[T - 1]]) T--;
            ARR[T++] = index;
        }

        int max(int[] nums)
        {
            return nums[ARR[H]];
        }

        void del(int index)
        {
            if (index == ARR[H]) H++;
        }
    }
}
